package bintree.heap.leetcode;

import java.util.*;

/**
 * 692. 前K个高频单词
 *
 * 加一个比较器
 * @author haomin
 * @date 2022/03/23 21:29
 **/
public class Num692_TopKFrequent {
    public List<String> topKFrequent(String[] words, int k) {
        Map<String,Integer> map = new LinkedHashMap<>();
        for(String i : words){
            int p = 1;
            if(map.containsKey(i)){
                int v = map.get(i);
                map.replace(i,v += 1);
            }else {
                map.put(i,p);
            }
        }

        Queue<Words> queue = new PriorityQueue<>(new WordsCom());

        Set<Map.Entry<String,Integer>> entries = map.entrySet();
        for(Map.Entry<String,Integer> s : entries){
            queue.offer(new Words(s.getKey(),s.getValue()));
        }

        List<String> ret = new ArrayList<>();
        for (int i = 0; i < k; i++) {
            Words words1 = queue.poll();
            String name = words1.getName();
            ret.add(name);
        }
        return ret;
    }
}

class WordsCom implements Comparator<Words> {
    @Override
    public int compare(Words o1, Words o2) {

        //当出现次数相等时，比较单词字母顺序
        if (o2.getTimes() == o1.getTimes()) {
            String version1 = o1.getName();
            String version2 = o2.getName();
            char[] data1 = version1.toCharArray();
            char[] data2 = version2.toCharArray();

            for (int n = 0; n < Math.max(version1.length(),version2.length()); n++) {
                int i = (n < data1.length ? (int)data1[n] : 0);
                int j = (n < data2.length ? (int)data2[n] : 0);

                if(i < j){
                    return -1;
                }else if(i > j){
                    return 1;
                }
            }
            return 0;
        }else {
            return o2.getTimes() - o1.getTimes();
        }
    }
}

class Words{
    private String name;
    private int times;

    public int getTimes() {
        return times;
    }

    public String getName() {
        return name;
    }

    public Words(String name, int times) {
        this.name = name;
        this.times = times;
    }
}